1. Field of the Invention
The present invention relates to a carry lookahead adder which is a binary digital arithmetical operation unit. The present invention also relates to a logical operation circuit suitable for use in the carry look-ahead adder.
2. Description of the Related Art
There has been heretofore known a ripple-carry adder which is used in a computer etc. The ripple-carry adder executes an addition of a given number of digits. The ripple-carry adder is constructed by sequentially connecting 1-bit full adders each for adding two 1-bit signals and a carry signal from a lower digit (carry-in) to output a sum and a carry signal to an upper digit (carry-out). The number of the 1-bit full adders corresponds to the number of digits (i.e. numbers of bits) of input signals to be added.
In the ripple-carry adder, before an addition in a certain digit place is started, it is necessary to determine a carry signal from the lower digit place. Thus, the operation time spent by the ripple-carry adder increases in proportion to the number of digits of input signals to be added. Therefore, the operation time of the ripple-carry adder lengthens as the number of processed bits increases.
In order to remove such a problem in the ripple-carry adder, it is known to apply a carry look-ahead system to an adder. According to the carry look-ahead system, before additions of bits of input signals to be added are implemented, each bit of the input signals is examined to generate a carry out.
In a typical carry look-ahead adder, the two input signals are divided into, for example, groups each consisting of 4 bits, and a carry-out to the next group is generated before the sum obtained in each group is outputted. The carry look-ahead adder is able to reduce the operation time (e.g. TOKKAIHEI 5-61643 patent publication).
One example of a conventional 32-bit carry look-ahead adder will be described hereafter with reference to FIG. 10.
It should be noted that, in the following description, an n bit indicates an n-th bit where the lowest bit is labeled as a 0 bit. In FIG. 10 and other Figs., among characters beginning with small character alphabets, characters such as a3:0 indicates a 3 bit to a 0 bit of a signal a.
In FIG. 10, there are 4-bit full adders (ADD: 4-bit ripple-carry adder) 30-0,30-1, . . . ,30-7, respectively. These 4-bit full adders 30-0 to 30-7 are provided for respective pairs of 4-bit signals a (a3:0,a7:4, . . . ,a31:28) and b (b3:0,b7:4, . . . ,b31:28) obtained by dividing two 32-bit input signals a31:0,b31:0 into 4-bit segments. The 4-bit full adders 30-0 to 30-7 receive 4-bit signals a,b of the corresponding groups and carry signals c (c-1,c3, . . . ,c27) from one lower digit than the lowest digit of the 4-bit signals a,b, and generate 4-bit carry generating signals g (g3:0,g7:4, . . . ,g31:28), 4-bit carry propagation signals p (p3:0,p7:0, . . . ,p31:28), and 4-bit summing signals s (s3:0,s7:4, . . . ,s31:28) by executing operation expressed in equations (1) to (4) indicated later.
In FIG. 10 and the following description, G3!, . . . ,G31!, P3!, . . . ,P31! indicate 1-bit carry generation signals and carry propagation signals, respectively.
It should be noted that in the equations indicated later, the symbol "* " indicates logical AND operation, the symbol "xor" indicates logical EXCLUSIVE-OR operation, the symbol "+" indicates logical OR operation, and the suffix "n" indicates the position (the place) of each bit in the input signals a,b to the 4-bit full adders 30-0 to 30-7. In addition, the numeral "0" corresponds to the lowest bit (the lowest digit), and the symbol "cn-1" indicates a carry signal from an (n-1)-th bit necessary to obtain a sum sn of n-th bits within the 4-bit full adders 30-0 to 30-7.
The equations (1) to (4) are given as: EQU gn=(an)*(bn) (1) EQU pn=(an)xor(bn) (2) EQU sn=(pn)xor(cn-1) (3) EQU cn=(gn)+(pn)*(cn-1) (4)
Next, 4-bit carry generation/propagation signal generators (4GP) 32-0,32-1, . . . ,32-7 form carry look-ahead circuits of a first part of a hierarchy. The 4-bit carry generation/propagation signal generators 32-0 to 32-1, . . . ,32-7 are provided in correspondence with the 4-bit full adders 30-0 to 30-7, respectively. The 4-bit carry generation/propagation signal generator 32-0, 32-1, . . . ,32-7 generates 1-bit carry generation signals Gn+3! (G3!,G7!, . . . ,G31!) and 1-bit carry propagation signals Pn+3! (P3!,P7!, . . . ,P31!) by executing operation in the following equations (5),(6) in response to 4-bit carry generation signals g (g3:0,g7:4, . . . ,g31:28) and 4-bit carry propagation signals p (p3:0,p7:4, . . . ,p31:28) generated by the corresponding 4-bit full adders 30-0 to 30-7, respectively, when the 4-bit input signals a (a3:0,a7:4, . . . ,a31:28) and b (b3:0,b7:4, . . . ,b31:28) are grouped into blocks. ##EQU1##
Further, in FIG. 10, carry look-ahead circuits 34-0,34-1, . . . ,34-7 (1CLA,2CLA,3CLA,4CLA,1CLA,2CLA,3CLA,4CLA) form a second part of the hierarchy.
The carry look-ahead circuits 34-0,34-1, . . . ,34-7 are provided in correspondence with the 4-bit full adders 30-0 to 30-7 and the carry generation/propagation signal generators 32-0 to 32-7.
Each of the carry look-ahead circuits from the first-stage to the fourth-stage (1CLA,2CLA,3CLA,4CLA) 34-0 to 34-3 receives a carry signal c-1 (i.e. a carry signal c-1 to the lowest digit of the 32-bit input signals a, b) to the lowest digit of the 4-bit full adder 30-0, carry generation signals Gn+3! (G3!,G7!,G11!,G15!), and carry propagation signals Pn+3! (P3!,P7!,P11!, P15!) generated by a circuit corresponding to each one within a carry generation/propagation generation circuit 32-0, 32-1, 32-2,or 32-3 and a circuit lower than that. In response to the received signals, each of the carry look-ahead circuits from the first-stage to the fourth-stage generates and outputs a carry signal c (i.e. each of carry signals (c3,c7,c11 ,c15) to be inputted to the 4-bit full adders 30-1 to 30-4 provided at the next-stages) from the uppermost bit of the 4-bit input signals a,b fed to the corresponding 4-bit full adders 30-0 to 30-3.
Likewise, each of the carry look-ahead circuits from the fifth-stage to the last (eighth)-stage (1CLA,2CLA,3CLA,4CLA) 34-4 to 34-7 receives a carry signal C15 (i.e. a carry signal generated by the carry look-ahead circuit 34-3) inputted to the 4-bit full adder 30-4 of the fifth stage, carry generation signals Gn+3! (G19!,G23!,G27!,G31!) and carry propagation signals Pn+3!, (P19!,P23!,P27!,P31!) generated by a circuit corresponding to each one within the carry generation/propagation signal generator 32-4 to 32-7. In response to the received signals, each of the carry look-ahead circuits from the fifth-stage to the last-stage generates and outputs a carry signal c (c19,c23,c27,c31) from the uppermost bits of the 4-bit input signals a,b to the corresponding 4-bit full adders 30-4 to 30-7. For example, carry signal c19 is generated by a combination of carry generation signal G19!, carry propagation signal P19!, and carry signal c15, and carry signal c31 is generated by a combination of carry generation signal G31!, carry propagation signals P19!, P23!, P27!, P31!, and carry signal c15. Then, carry signals c19,c23,c27 generated by the carry look-ahead circuits 34-4,34-5,34-6 other than that generated by the last-stage are inputted to the 4-bit full adders 30-5,30-6,30-7 of the next stage, respectively.
Here, if the carry generation signals G3!,G7!,G1 1!,G15! are expressed as G&lt;0&gt;,G&lt;1&gt;, . . . from the lower digit G3! in that order and the carry propagation signals P3!,P7!,P11!,P15! as P&lt;0&gt;,P&lt;1&gt;, . . . and the carry signal c-1 as Cin, each of the look-ahead circuits 34-0 to 34-3 generates the carry signal c (c3,c7,c11 ,c15) by executing the operation given in an equation (7) indicated later. Similarly, if the carry generation signals G19!,G23!,G27!,G31! are expressed as G&lt;0&gt;,G&lt;1&gt;, . . . from the lower digit and the carry propagation signals P19!,P23!, P27!,P31! as P&lt;0&gt;,P&lt;1&gt;, . . . from the lower digit P19! in that order and the carry signal c15 as Cin, each of the carry look-ahead circuits 34-4 to 34-7 generates a carry signal c (c19,c23,c27,c31) by executing the operation given in the following equation (7): ##EQU2##
Accordingly, for example, in the carry look-ahead circuit 34-0, a carry signal c3 is generated as shown by an equation (8) indicated later. In the carry look-ahead circuit 34-1, a carry signal c7 is generated as shown by an equation (9) indicated later. In the carry look-ahead circuit 34-2,a carry signal c11 is generated as shown by an equation (10) indicated later. In the carry look-ahead circuit 34-3, a carry signal c15 is generated as shown by an equation (11) below: ##EQU3##
Namely, as can be seen from the foregoing equations (1),(2),(5) to (11), a carry generating signal gn and a carry propagation signal pn depend on only the two input signals a,b, and thus, they can be obtained for each digit in parallel. What is more, by using only the carry generating signal gn, the carry propagating signal pn, and the carry signal c-1 inputted to the 4-bit full adder 30-0 of the lowest digit, it is possible to generate the carry signals c3,c7, . . . ,c27 to be inputted to the 4-bit full adders 30-1 to 30-7 other than that of the lowest digit.
In the 32-bit adder of FIG. 10, carry signals are fed to the 4-bit full adders 30-4 to 30-7 in advance as will be explained below. The carry generation/propagation signal generator 32-0 and the carry look-ahead circuit (1CLA) 34-0 cooperate to look ahead a carry c3 from the third bit (fourth digit) of the input signals a,b, and the carry c3 is inputted to the 4-bit full adder 30-1 of the second-stage.
The operations of carry generation/propagation signal generators 32-4 to 32-7 and carry look-ahead circuits 34-4 to 34-7, which correspond to the 4-bit full adders 30-4 to 30-7 from the fifth stage to the eighth-stage, are similar to the operations of those corresponding to the 4-bit full adders 30-0 to 30-3 from the first-stage to the four-stage.
The adder employing such a carry look-ahead method can shorten the calculation time as compared with a ripple carry adder because a carry signal from a lower digit can be inputted to the 4-bit full adder (ADD) 30 of the upper digit before the 4-bit full adder (ADD) 30 of the lower digit generates a sum.
There are, however, the following disadvantages even in the conventional adder employing the above-mentioned carry look-ahead method.
With reference to FIG. 10, a consideration will now be given of a portion that constitutes the 8 bit carry look-ahead adder enclosed by a dash-dot-line, that is, the portion consisting of the 4-bit full adders (ADD) 30-0,30-1, the carry generation/propagation signal generators (4GP) 32-0,32-1, and carry look-ahead circuits (1CLA,2CLA) 34-0,34-1 from the first-stage to the second-stage.
In such a carry look-ahead adder (hereafter referred to as "CLA adder"), a time T required for calculating a sum s7 of the highest bit (the seventh bit) after the two 8-bit input signals a7:0,b7:0 and a carry signal c-1 from the lower digit are inputted, that is, a time T required for completing 8-bit addition, is expressed by the following equation (12). Here, the symbol "+" indicates addition in the equation (12) only. EQU T=t1+t2+t3+t4 (12)
where
t1=(a time required for the generation of the 4-bit carry generation signal g3:0 and the 4-bit carry propagation signal p3:0 by the 4-bit full adder 30-0 of the first-stage); PA1 t2=(a time required for the generation of the 1-bit carry generation signal G3! and the 1-bit carry propagation signal P3! by the carry generation/propagation signal generator 32-0); PA1 t3=(a time required for the generation of the carry signal c3 by the carry look-ahead circuit 34-0 of the first-stage); and PA1 t4=(a time required for the full addition of 4 upper bits a7:4,b7:4 of the input signals a,b and for the generation of a sum on the basis of the carry signal c3 by the 4-bit full adder 30-1 of the second-stage).
That is to say, in the above conventional 8-bit CLA adder, the carry look-ahead adder circuit 34-0 of the first-stage generates a carry signal c3 for the 4-bit full adder 30-1 of the second-stage before the 4-bit full adder 30-0 of the first-stage completes the full addition of 4 lower bits a3:0,b3:0 (t1+t2+t3). Then, the 4-bit full adder 30-1 of the second-stage executes the full addition of 4 upper bits a7:4,b7:4 after the carry look-ahead circuit 34-0 of the first-stage generates a carry signal c3.
Accordingly, in the conventional CLA adder, as can be seen from the foregoing equation (12), although a carry signal from a lower digit to a upper digit can be quickly generated, the 4-bit full adder of an upper digit (ADD) 30 is required to execute the full addition after a carry signal from a lower digit is determined.
Therefore, there is a limit to reduction of the calculation time required for the generation of the summing signal of full bits.
The present invention is made in consideration of these problems and disadvantages. An object of the present invention is to provide a carry look-ahead adder capable of further shortening the calculation time. Another object of the present invention is to provide a logical operation circuit for use in the carry look-ahead adder.